package everydayone.decodeString;

import java.util.LinkedList;

/**
 * @Date 2020/05/28
 * @author 王光浩
 * @Thinking 使用 两个 栈，一个数字栈，一个 StringBuilder 栈，一个 int vaule （保存重复次数）
 * 		（1）当前字母是 数字 ： value*10+当前数字
 * 		（2）当前字母是 ‘[’ ：  在 Stringbuilde 栈中添加一个 StringBuilder 对象。将 value 加入到 数字栈
 * 		（3）当前字母是‘]’：从数字栈中取出栈顶元素k,从StringBuilder 栈中取出栈对象 s,将 s重复 k 遍，然后加入到 栈顶元素
 * 			中，如果栈为空，则返回该值
 *		（4）否则将当前元素 加入到 栈顶的 StringBuilder对象中。
 * @Analysis 时间复杂度O（n*m），空间复杂度O（n）
 */ 
public class MyMethodOne {
	public String decodeString(String s) {
		LinkedList<Integer> stackNum = new LinkedList<Integer>();
		LinkedList<StringBuilder> stackStr = new LinkedList<StringBuilder>();
		int value = 0;
		stackNum.push(1);
		stackStr.push(new StringBuilder());
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			//如果为数组，进行累加
			if (c >= '0' && c <= '9')
				value = value * 10 + (c-'0');
			//如果为'['
			else if (c == '[') {
				stackNum.push(value);
				stackStr.push(new StringBuilder());
				value = 0;
			}
			//如果为']'
			else if (c == ']') {
				int topNum = stackNum.poll();
				StringBuilder topStr = stackStr.poll();
				String original = topStr.toString();
				for (int j = 0; j < topNum; j++)
					topStr.append(original);
				stackStr.peek().append(topStr);
			}
			//否则为字母
			else 
				stackStr.peek().append(c);
		}
        return stackStr.poll().toString();
    }
}
